// 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

// 输入：head = [1,2,3,4,5], left = 2, right = 4
// 输出：[1,4,3,2,5]
// 示例 2：

// 输入：head = [5], left = 1, right = 1
// 输出：[5]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
//方法一：迭代（两次遍历）
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
  const dummyNode = new ListNode(-1)
  dummyNode.next = head
  let pre = dummyNode
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next
  }
  let rightNode = pre
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next
  }
  let leftNode = pre.next
  let curr = rightNode.next
  pre.next = null
  rightNode.next = null
  reverseLinkList(leftNode)
  pre.next = rightNode
  leftNode.next = curr
  return dummyNode.next
};
var reverseLinkList = function (cur) {
  let pre = null
  let p = cur
  while (p) {
    const nxt = p.next
    p.next = pre
    pre = p
    p = nxt
  }
}
// 复盘：
// 1、因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
// 2、从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
// 3、从 pre 再走 right - left + 1 步，来到 right 节点
// 4、记录下left节点、left的前一个节点、right节点以及right的后一个节点
// 5、切割链表
// 6、对链表进行反转
// 7、连接链表


// 方法二：头插法（一次遍历）
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function (head, left, right) {
  const dummyNode = new ListNode(-1)
  dummyNode.next = head
  let pre = dummyNode
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next
  }
  let cur = pre.next
  for (let i = 0; i < right - left; i++) {
    let next = cur.next
    cur.next = next.next
    next.next = pre.next
    pre.next = next
  }
  return dummyNode.next
}
// 复盘：
// 1、因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
// 2、从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
// 3、先记录当前节点的下一个节点为next，当前节点的前一节点pre
// 4、让当前节点指向next的下一个节点
// 5、让next指向当前节点
// 6、让当前节点的前一个节点指向next
